문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 점근 표기법 (문단 편집) == 컴퓨터 과학에서의 점근 표기법 == 일반적으로 [[알고리즘]]의 시간복잡도를 나타내는데 사용된다. '''Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 [[시간복잡도]]를 가진다는 의미이다.''' 물론 공간복잡도에 대해서도 사용될 수 있다. 사실 공간복잡도의 이론적인 상한은 시간복잡도이기 때문에 [* 메모리를 할당하는 것도 일종의 명령어이기 때문에 컴퓨터는 시간을 초월한 넓이의 공간을 접근하지 못한다. [[튜링 머신]]에서 테이프를 옮기는 동작과 연산을 하는 동작 사이에 원론적이 구분이 없다는 점을 들어 이해할 수 있다. ] 시간복잡도가 공간복잡도보다 조금 더 중요하게 취급받는다. 사실 현업에서는 알고리즘이 2배, 3배, 상수배 빨라지는 것도 의미가 있고, 당연히 계산 Step의 개수를 정확히 센 결과가 Asymptotic보다 더 정확한 지식이다. 하지만 이걸 쓰는 이유는 [math(n)]이 커지면 커질수록 언젠가는 Big-O 복잡도가 큰 알고리즘이 Big-O 복잡도가 작은 알고리즘을 역전한다는 수학적인 사실이 있기 때문에 생기는 원론적인 구분이 가능하다는 것이다. 예를 들면 극단적으로 [math(9999n)]개의 step이 필요한 알고리즘이 [math(0.001n^2)] 보다 느려 보이더라도 [math(n)]이 커질 때 언젠가는 [math(0.001n^2)]의 알고리즘이 역전한다는 것이다. 이건 다항 알고리즘과 지수 알고리즘의 차이에서도 존재하고 [math(2^{0.001n})]처럼 아무리 상수항이 작은 지수 알고리즘이라도 언젠가는 [math(n^{9999})]보다 느려지는 시점이 올 수밖에 없다. 이 때문에 수많은 수학자들이 최대한 선형 알고리즘을 찾거나 그게 아니더라도 다항 알고리즘을 찾으려고 고생하는 이유이기도 하고, [[P-NP 문제]]가 중요한 이유이기도 하다. Big-O 계산의 예시로는 [math(O(5n+7)=O(5n)=O(n))]이 되고, [math(O(n^2+25)=O(n^2))]을 들 수 있다. 여기서 등호 기호([math(=)])를 '같다(equals)'는 뜻이 아니라 '~이다(is)', '~쯤 된다(approx)'라고 해석하면 기호의 혼란을 피할 수 있다. 경우에 따라 [math(O(g(n)) )]을 하나의 [[집합]]으로 보고 [math(f(n) \in O(g(n)) )]으로 표기하기도 하는데, 과거보다 현대로 올수록 많은 알고리즘, 미적분학, 해석학 교과서들이 이 집합 개념을 사용하고 있다. 보다 수학적으로 엄밀해지고, asymptotic tight bound를 정확히 특정하는 Big-θ 표기법에서는 [math(\theta(g(n)) )]을 간단히 [math(O(g(n))\cap\Omega(g(n)) )]으로 정의할 수 있다. [math(f(n)=O(g(n)) )]에서 등호는 [math(\in)]의 의미를 imply하며 동시에 직관성을 얻는다. 이 '같다'의 직관성은 Big-O notation의 오용을 초래[* 선형대수학에서 생성기저에 대해 다루는 경우에도 이와 같은 등호 기호의 오남용을 볼 수 있다. ]했고, Big-Theta notation을 탄생하게 한 배경이 되었다. [[파일:2-4-1.png|width=400]] 간단한 예를 한번 들어보자. 디스크에 있는 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자. 그림에서 파일 크기가 작다면, 즉 [math(n)]이 작다면 [math(O(n))]의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다(비용은 고려하지 않는다면).[* 실제로 구글 및 NASA 등 [[페타#s-1|PB]] 단위로 데이터를 취급하는 단체, 업체들이 이렇게 데이터를 항공 운반하는 경우가 자주 있다.] 파일이 아무리 커도, 즉 [math(n)]이 아무리 커도 비행기를 통한 파일 전송은 [math(O(1))]로 항상 일정한 시간이 소요되기 때문이다. 이것이 바로 점근적 실행 시간이며, 빅오는 점근적 실행 시간을 표기하는 방법 중 하나다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기